# -*- encoding: utf-8 -*-
"""
二叉查找树：
树中的任意节点，其左子树中的每个节点的值都小于该节点的值，其右子树中的每个节点的值都大于该节点的值
"""


class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None


class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def is_empty(self):
        if self.root:
            return False
        return True

    def insert(self, data):
        new_node = Node(data)
        parent_node = None
        if self.is_empty():
            self.root = new_node
        else:
            current_node = self.root
            while current_node is not None:
                parent_node = current_node
                if data > current_node.data:
                    current_node = current_node.right
                else:
                    current_node = current_node.left
            if data > parent_node.data:
                parent_node.right = new_node
            else:
                parent_node.left = new_node
            new_node.parent = parent_node

    def delete(self, data):
        """
         Example：
                  8
                 / \
                3   10
               / \    \
              1   6    14
                 / \   /
                4   7 13
        Example After Deletion：
                  4
                 / \
                1   7
        """
        if not self.is_empty():
            node = self.get_node(data)
            if node is not None:
                if node.left is None and node.right is None:
                    parent_node = node.parent
                    if parent_node is not None:
                        if parent_node.left is node:
                            parent_node.left = None
                        else:
                            parent_node.right = None
                elif node.left is not None and node.right is None:
                    parent_node = node.parent
                    if parent_node is not None:
                        if parent_node.left is node:
                            parent_node.left = node.left
                        else:
                            parent_node.right = node.left
                        node.left.parent = parent_node
                    else:
                        self.root = node.left
                elif node.left is None and node.right is not None:
                    parent_node = node.parent
                    if parent_node is not None:
                        if parent_node.left is node:
                            parent_node.left = node.right
                        else:
                            parent_node.right = node.right
                        node.right.parent = parent_node
                    else:
                        self.root = node.right
                else:
                    min_right_node = node.right
                    while min_right_node.left is not None:
                        min_right_node = min_right_node.left
                    template = min_right_node.data
                    self.delete(template)
                    node.data = template

    def get_node(self, data):
        current_node = None
        if not self.is_empty():
            current_node = self.root
            while current_node is not None:
                if current_node.data == data:
                    return current_node
                if data > current_node.data:
                    current_node = current_node.right
                else:
                    current_node = current_node.left
        return current_node

    def __InOrderTraversal(self, curr_node):
        nodeList = []
        if curr_node is not None:
            nodeList.insert(0, curr_node)
            nodeList = nodeList + self.__InOrderTraversal(curr_node.left)
            nodeList = nodeList + self.__InOrderTraversal(curr_node.right)
        return nodeList

    def __str__(self):
        list = self.__InOrderTraversal(self.root)
        content = ""
        for x in list:
            content = content + " " + str(x.data)
        return content


def testBinarySearchTree():
    t = BinarySearchTree()
    t.insert(8)
    t.insert(3)
    t.insert(6)
    t.insert(1)
    t.insert(10)
    t.insert(14)
    t.insert(13)
    t.insert(4)
    t.insert(7)

    print(t.__str__())

    if t.get_node(6) is not None:
        print("The label 6 exists")
    else:
        print("The label 6 doesn't exist")

    if t.get_node(-1) is not None:
        print("The label -1 exists")
    else:
        print("The label -1 doesn't exist")

    t.delete(13)
    t.delete(10)
    t.delete(8)
    t.delete(3)
    t.delete(6)
    t.delete(14)

    print(t.__str__())


if __name__ == '__main__':
    testBinarySearchTree()
